import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Radix {
    public static void radixSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }
        // 循环取得数组中的最大值
        int maxNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }
        // 根据最大值算出数组中的最大位数，个位、十位、百位、千位等
        int maxDigit = 0;
        while (maxNum != 0) {
            maxNum /= 10;
            maxDigit++;
        }
        // 初始化10个list，分别存放位数是0-9的10组数字
        List<List<Integer>> buckets = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }
        int mod = 10; // 初始10，用于数据个位数取模
        int div = 1; // 桶序号除数
        // 按位数循环数组，个位循环1次，十位循环2次，百位循环3次，以此类推！
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            // 循环数组，将数据分别存入桶中
            // 第一次循环，桶里面的个位数顺序排序完成
            // 第二次循环，个位、十位都排序完成
            // 第三次循环，个位、十位、百位都排序完成
            for (int j = 0; j < arr.length; j++) {
                // 计算当前位数的桶序号
                int bucketIndex = (arr[j] % mod) / div;
                buckets.get(bucketIndex).add(arr[j]);
            }
            // 循环桶列表，将当前位数已排序的数据放入数组中
            int currentIndex = 0;
            for (int j = 0; j < 10; j++) {
                List<Integer> bucket = buckets.get(j);
                for (int k = 0; k < bucket.size(); k++) {
                    arr[currentIndex++] = bucket.get(k);
                }
                bucket.clear();
            }
        }
    }

    public static void main(String[] args, Object Assertions) {
        int[] arr = {5, 2, 8, 3, 12, 35, 57, 1, 6};
        int[] expectedArr = {1, 2, 3, 5, 6, 8, 12, 35, 57};
        Radix.radixSort(arr);
        System.out.println("arr = " + Arrays.toString(arr));
    }
}

